/*************************************************************************
> File Name: quick_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-21 11:31:15
> Description:  快速排序
************************************************************************/

#include "general.h"

#include <stdio.h>

int quickSort(int arr[], int begin, int end);
int partition(int arr[], int bengin, int end);

int main(int argc, char const *argv[])
{
    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    quickSort(arr, 0, size - 1);
    printf("Sorted array: \n");
    printArr(arr, size);
    return 0;
    return 0;
}

int quickSort(int arr[], int begin, int end)
{
    // 划分成两个部分
    if (begin < end)
    {
        int mid = partition(arr, begin, end);
        quickSort(arr, begin, mid - 1);
        quickSort(arr, mid + 1, end);
    }
}
int partition(int arr[], int bengin, int end)
{
    int sign = arr[end];
    int i = bengin - 1; // begin-1开始
    for (int j = bengin; j < end; j++)
    {
        if (arr[j] <= sign) // 如果小于等于基准，交换到i+1和
        {
            swap(&arr[++i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[end]); // 将基准放置到下一个位置
    return i + 1;
}
